/** ***************************************************************************
 * CoffeeHeapsort.hpp
 * 2012 CoffeeParty Ltd.
 * Date Created: 2012-08-01                                  format YYYY-MM-DD
 * Revision Id: $Id$
 ******************************************************************************
 */

#ifndef _COFFEE_HEAPSORT_HPP_
#define _COFFEE_HEAPSORT_HPP_

#include "CoffeeCommons.hpp"

template<class T>
inline void c_heapsink(T *array, int element, int max)
{
    while ((element << 1) < max)
    {
        int j = (element << 1);
        if (j + 1 < max && array[j] < array[j + 1])
            j = j + 1;

        if (array[element] < array[j])
        {
            T t = array[j];
            array[j] = array[element];
            array[element] = t;
            element = j;
        }
        else return;
    }
}

template<class T>
inline void c_heapsort(T *_array, int size)
{
    T *virtualArray = _array - 1;
    int virtualSize = size + 2;
    int i = 0;

    ///< Build Heap
    for (i = ((size - 1) / 2); i >= 0; --i)
        c_heapsink(virtualArray, i + 1, virtualSize - 1);

    ///< Sort Array
    for (i = (size - 1); i > 0; --i)
    {
        T t = _array[0];
        _array[0] = _array[i];
        _array[i] = t;
        c_heapsink(virtualArray, 1, i + 1);
    }
}

#endif /** _COFFEE_HEAPSORT_HPP_ */
